#include <bits/stdc++.h>
using namespace std;

// 最短路 Dijkstra算法

using ll = long long;

const int N = 100005, M = 200005;
struct Edge
{
    ll v, w, next;
} edge[M];
ll head[N], idx;
ll u, v, w;
ll d[N], vis[N];

void add(ll u, ll v, ll w)
{
    edge[++idx].v = v;
    edge[idx].w = w;
    edge[idx].next = head[u];
    head[u] = idx;
}

void dijkstra(ll s, ll n)
{
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
    for (ll i = 0; i <= n; i++)
    {
        d[i] = LLONG_MAX;
    }
    d[s] = 0;
    pq.push({0, s});
    while (!pq.empty())
    {
        ll u = pq.top().second;
        pq.pop();
        if (vis[u])
            continue;
        vis[u] = 1;
        for (ll e = head[u]; e; e = edge[e].next)
        {
            ll v = edge[e].v, w = edge[e].w;
            if (d[v] > d[u] + w)
            {
                d[v] = d[u] + w;
                pq.push({d[v], v});
            }
        }
    }
}

int main()
{
    ll n, m, s;
    cin >> n >> m >> s;
    for (int i = 0; i < m; i++)
    {
        cin >> u >> v >> w;
        add(u, v, w);
    }
    dijkstra(s, n);
    for (int i = 1; i <= n; i++)
    {
        cout << d[i];
        if (i != n)
            cout << " ";
    }
    system("pause");
    return 0;
}